翻訳と辞書 Words near each other ・ Padded Lilies ・ Padded mailer ・ Padded Room (mixtape) ・ Padded V-hull ・ Padden ・ Paddenswick Road tube station ・ Paddhari ・ Paddi Edwards ・ Paddi Khalsa ・ Paddick ・ Paddie Bell ・ Paddie O'Neil ・ Padding ・ Padding (cryptography) ・ Padding (disambiguation) ・ Padding argument ・ Padding oracle attack ・ Paddington ・ Paddington (1975 TV series) ・ Paddington (disambiguation) ・ Paddington (film) ・ Paddington (UK Parliament constituency) ・ Paddington Academy ・ Paddington alcohol test ・ Paddington Arm ・ Paddington Basin ・ Paddington Bear ・ Paddington Bear (1989 TV series) ・ Paddington Bear's Gold Record ・ Paddington Gold Mine Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Padding argument ： ウィキペディア英語版 Padding argument In computational complexity theory, the padding argument is a tool to conditionally prove that if some complexity classes are equal, then some other bigger classes are also equal. == Example == The proof that P = NP implies EXP = NEXP uses "padding". $\backslash mathrm\; \backslash subseteq\; \backslash mathrm$ by definition, so it suffices to show $\backslash mathrm\; \backslash subseteq\; \backslash mathrm$. Let ''L'' be a language in NEXP. Since ''L'' is in NEXP, there is a non-deterministic Turing machine ''M'' that decides ''L'' in time $2^$ for some constant ''c''. Let : $L\text{'}=\backslash ,$ where ''1'' is a symbol not occurring in ''L''. First we show that $L\text{'}$ is in NP, then we will use the deterministic polynomial time machine given by P = NP to show that ''L'' is in EXP. $L\text{'}$ can be decided in non-deterministic polynomial time as follows. Given input $x\text{'}$, verify that it has the form $x\text{'}\; =\; x1^$ time, which is polynomial in the size of the input, $x\text{'}$. So, $L\text{'}$ is in NP. By the assumption P = NP, there is also a deterministic machine ''DM'' that decides $L\text{'}$ in polynomial time. We can then decide ''L'' in deterministic exponential time as follows. Given input $x$, simulate $DM(x1^\{2^\{|x|^c\}\})$. This takes only exponential time in the size of the input, $x$. The $1^d$ is called the "padding" of the language ''L''. This type of argument is also sometimes used for space complexity classes, alternating classes, and bounded alternating classes. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Padding argument」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.